0885. 螺旋矩阵 III【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟

1. 📝 题目描述

• leetcode

在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，我们到过网格的所有 rows x cols 个空间。

按照访问顺序返回表示网格位置的坐标列表。

---

示例 1：

输入：rows = 1, cols = 4, rStart = 0, cStart = 0
输出：[
  [0, 0],
  [0, 1],
  [0, 2],
  [0, 3]
]

示例 2：

输入：rows = 5, cols = 6, rStart = 1, cStart = 4
输出：[
  [1, 4],
  [1, 5],
  [2, 5],
  [2, 4],
  [2, 3],
  [1, 3],
  [0, 3],
  [0, 4],
  [0, 5],
  [3, 5],
  [3, 4],
  [3, 3],
  [3, 2],
  [2, 2],
  [1, 2],
  [0, 2],
  [4, 5],
  [4, 4],
  [4, 3],
  [4, 2],
  [4, 1],
  [3, 1],
  [2, 1],
  [1, 1],
  [0, 1],
  [4, 0],
  [3, 0],
  [2, 0],
  [1, 0],
  [0, 0]
]

---

提示：

• 1 <= rows, cols <= 100
• 0 <= rStart < rows
• 0 <= cStart < cols

2. 🎯 s.1 - 模拟

c

int** spiralMatrixIII(int rows, int cols, int rStart, int cStart, int* returnSize, int** returnColumnSizes) {
    int total = rows * cols;
    int** res = (int**)malloc(sizeof(int*) * total);
    *returnColumnSizes = (int*)malloc(sizeof(int) * total);
    *returnSize = 0;
    int dr[] = {0, 1, 0, -1}, dc[] = {1, 0, -1, 0};
    int r = rStart, c = cStart, d = 0, steps = 1;
    res[*returnSize] = (int*)malloc(sizeof(int) * 2);
    res[*returnSize][0] = r; res[*returnSize][1] = c;
    (*returnColumnSizes)[*returnSize] = 2;
    (*returnSize)++;
    while (*returnSize < total) {
        for (int t = 0; t < 2; t++) {
            for (int i = 0; i < steps; i++) {
                r += dr[d]; c += dc[d];
                if (r >= 0 && r < rows && c >= 0 && c < cols) {
                    res[*returnSize] = (int*)malloc(sizeof(int) * 2);
                    res[*returnSize][0] = r; res[*returnSize][1] = c;
                    (*returnColumnSizes)[*returnSize] = 2;
                    (*returnSize)++;
                }
            }
            d = (d + 1) % 4;
        }
        steps++;
    }
    return res;
}

js

/**
 * @param {number} rows
 * @param {number} cols
 * @param {number} rStart
 * @param {number} cStart
 * @return {number[][]}
 */
var spiralMatrixIII = function (rows, cols, rStart, cStart) {
  const res = [[rStart, cStart]]
  const dr = [0, 1, 0, -1],
    dc = [1, 0, -1, 0]
  let d = 0,
    steps = 1
  let r = rStart,
    c = cStart
  while (res.length < rows * cols) {
    for (let t = 0; t < 2; t++) {
      for (let i = 0; i < steps; i++) {
        r += dr[d]
        c += dc[d]
        if (r >= 0 && r < rows && c >= 0 && c < cols) res.push([r, c])
      }
      d = (d + 1) % 4
    }
    steps++
  }
  return res
}

py

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        res = [[rStart, cStart]]
        dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
        d, steps = 0, 1
        r, c = rStart, cStart
        while len(res) < rows * cols:
            for _ in range(2):
                for _ in range(steps):
                    r += dr[d]; c += dc[d]
                    if 0 <= r < rows and 0 <= c < cols:
                        res.append([r, c])
                d = (d + 1) % 4
            steps += 1
        return res

• 时间复杂度：$O(max(rows,cols{)}^2)$，螺旋覆盖的最大范围
• 空间复杂度：$O(rows\times cols)$，存储结果

算法思路：

• 从起点开始按顺时针螺旋行走，每两个方向后步长 +1
• 只记录落在矩阵范围内的坐标